package leetcode.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2023/11/12 22:11
 */
public class _797 {
    List<List<Integer>> res;

    /**
     * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
     * <p>
     * graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
     */
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        track(graph,0,path);
        return res;
    }

    private void track(int[][] graph, int i, LinkedList<Integer> path) {
        path.add(i);
        if (i == graph.length-1){
            res.add(new LinkedList<>(path));
        }
        for (int j : graph[i]) {
            track(graph,j,path);
        }
        path.removeLast();
    }
}
